1. Field of the Invention
The present invention relates to a device and method for creating a virtual LAN and a network system which provides virtual LAN services. In particular, this present invention relates to a device and method for creating virtual LAN implementing the multiple spanning tree protocol and a network system which provides virtual LAN services implementing the multiple spanning tree protocol.
2. Description of the Related Art
In recent years, due to the implementation of the Gigabit-class Ethernet (registered trademark) technology standardized by the IEEE, virtual LAN (VLAN) services which utilize Ethernet over a comparably wide area and services providing virtual private networks (VPN) are receiving attention. In addition, communication networks for providing these services are established by connecting multiple nodes (bridge node) in a mesh form.
Each node is, for example, a switch and generally comprises a plurality of input/output ports. Therefore, if the paths by with traffic flows are not restricted, traffic circulates a looped path, and a situation wherein the traffic of the entire network increases may occur. In extreme cases, the frame for transmitting traffic is saturated by traffic circulating the looped path, and the communication performance of the network may be lost.
Therefore, in bridged networks of this type, it is necessary to prevent the looped links. IEEE 802.1d-compliant spanning tree protocol (STP) is known as a technology for the prevention thereof.
The spanning tree protocol first determines a root node and defines a spanning tree by selecting links from the root node in a tree form. Each node operates to prohibit the flow of traffic to links other than that included in the defined spanning tree. This operation is realized, for example, by discarding traffic received from a link which is not included in the spanning tree at each node. Procedures such as this prevent the formation of loops.
Furthermore, the spanning tree protocol is extremely effective in operating and managing the network when a node failure occurs, because it has functions which autonomously recreate trees between nodes, and is widely utilized in bridged networks.
When providing virtual LAN services using a bridged network, the traffic of the user receiving the service flows along the tree configured by the spanning tree protocol, between the nodes accommodating the users. However, with the spanning tree protocol, links which are not used at all may exist within the network. This is not beneficial to the operation of the network and is a problematic issue of the spanning tree protocol which should be remedied.
In IEEE 802.1s, multiple spanning tree protocol (MSTP) is standardized as the improved version of the spanning tree protocol. Here, the multiple spanning tree protocol is a protocol which configures a plurality of trees which differ from each other to the assigned network and enables simultaneous operation. It is also considered that efficient use of network resources can be made by implementing this protocol. However, details regarding the configuration methods for implementing multiple spanning tree protocol are beyond the provisions of IEEE, and detailed methods have not yet been determined.
In addition, the paths through which virtual LAN traffic flows (virtual LAN topology) are determined uniquely according to the spanning trees. Therefore, in networks where only one spanning tree is configured, it is not necessary for the network administrator to design a virtual LAN topology. However, in a network operated by multiple spanning tree protocol, a plurality of virtual LAN topologies which differ from each other may exist because a plurality of trees maybe configured. Therefore, the network administrator must determine how to configure the trees to flow virtual LAN traffic, or in other words, how to design the virtual LAN topology.
In order to design a virtual LAN topology so that network resources are effectively used, it is thought that the formation of the spanning trees and the design of the virtual LAN topology should be performed using the following procedures (1) to (4):
(1) Define cost based on the prescribed communication parameter of each link. Here, the cost of the link is a monotonically increasing function which has a positive correlation to the communication parameter.
(2) Form a sub-tree which connects the user accommodating nodes on the assigned virtual LAN with minimum cost as the virtual LAN topology.
(3) Form the spanning tree according to the virtual LAN topology obtained in (2) above.
(4) Accommodate the assigned virtual LAN traffic to the spanning tree obtained in (3) above.
The information used to define the cost in (1) is SET, for example, utilizing a keyboard and the like by the network administrator. However, a configuration wherein a device which collects statistical information regarding network operation is provided on the network, and necessary information is set to each node from this device, can also be considered. This configuration can be actualized by, for example, a certain node collects statistical information and sends setup information to each node.
The procedure (2) above is a Steiner Tree problem which determines the sub-tree to connect some of the nodes within the network, and because no method for solving this in actual time exists, a heuristic search method is implemented.
As a method for finding the sub-tree with the lowest cost, the Rayward-Smith method (hereinafter, RS method) which is widely used as a heuristic solution for Steiner Tree problems is implemented. With the RS method, first, a set including a plurality of single node trees which are made up of nodes (in this case, more than two user accommodated nodes) to be comprised in the sub-tree are prepared. Next, nodes (called relay node) other than those which are comprised in each of the single node trees are selected one by one, and one tree is formed by connecting the single node trees together via the selected relay nodes. The search process is completed when all of the single node trees are comprised in one tree. Here, nodes which have the smallest increase in link cost when being added to the tree is selected as the selected relay nodes. In other words, the node with the smallest value when the sum of the link costs between each user accommodated node and relay node is divided by the number of user accommodated nodes is selected. As a result, the sub-tree with the lowest cost can be found.
After the sub-tree with the lowest cost (virtual LAN topology) which includes user accommodated nodes is obtained using the RS method, the remaining nodes which are not comprised in the virtual LAN topology are added one by one to the virtual LAN topology in order, starting from the node with the smallest increase in cost when being added to the virtual LAN topology. At this time, it is presumed that a closed path has not been formed. This procedure is realized by, for example, the J.B. Kruskal algorithm and R.S. Prime algorithm. This becomes a spanning tree when all nodes have been comprised in the tree.
By mapping the virtual LAN to the spanning tree obtained by the procedures above, effective use of network resources can be made.
In regards to multiple spanning tree protocol, it is stated in detail in the Non-Patent Document 1. However, this protocol is a new technology, and published patent references could not be found at this time. Furthermore, in regards to the RS method, it is stated in Non-patent Document 2.    Non-Patent Document 1    IEEE P802.1s/D15 “Multiple Spanning Trees”    Non-patent Document 2    IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS Vol.6 No.9, December 1988, p.1617-1622, “Routing of Multipoint Communications” (Bernard M. Waxman)
However, when virtual LAN topology is designed using the procedures above, it is known that, in regards to the search for the sub-tree with the lowest cost through RS method, the larger the ratio of the number of nodes in the sub-tree to the total number of nodes in the network, the more its search calculation time increases exponentially. Therefore, if this search process is performed when the request for the creation of a virtual LAN is received from the user, the time required until the virtual LAN service is provided increases enormously, and the network becomes unstable, if there are large numbers of user storage nodes. In addition, because several seconds to several tens of seconds are required until service operation is possible after necessary information has been set in the nodes, if the spanning tree is newly set for each individual virtual LAN, additional waiting period is generated until service provision can commence.
Furthermore, in searches implementing the RS method, although the sub-tree with the lowest cost can be found, it is impossible to find the sub-tree with an arbitrary nth lowest cost. Therefore, in the means for finding spanning trees using the RS method, alternative virtual LAN topologies and/or spanning trees which effectively use communication resources cannot be designed, when the requested virtual LAN service cannot be accommodated due to insufficient available bandwidth in the link on the path.